package tree;

/**
 * 题目：二叉搜索树的后序遍历序列
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。假设输入的数组的任意两个数字都互不相同。
 * @Author Gavin
 * @date 2022.08.06 22:04
 */
public class tree_23 {
    /**
     * <p>
     * 解题思路：
     * 1. 确定root节点（后续遍历，说明最后一个节点就是根节点）
     * 2. 根节点左边的节点比根节点小，右边的比根节点大，所以根据这个特性把序列分成两段
     * 3. 判断上一步中分开的两段中是否有比根节点大或者根节点小的，如果左边有比根节点大或者右边有比根节点小的就返回false
     * 4. 左右两边再递归1，2，3步骤
     */
    public boolean solution(int[] post) {
        if (post == null || post.length == 0) return false;
        return helpVerify(post, 0, post.length - 1);
    }
    public boolean helpVerify(int[] post, int start, int end) {
        if (start >= end) return true;
        int rootIndex = post[end];
        int i;
        //找到左右子数的分界点
        for (i = start; i < end; i++)
            if (post[i] > rootIndex)
                break;
        //在右子树中判断是否含有小于root的值，如果有返回false
        for (int j = i; j < end; j++)
            if (post[j] < rootIndex)
                return false;
        return helpVerify(post, start, i - 1) && helpVerify(post, i, end - 1);
    }
}
